package com.zx._12_算法.algorithm.letcode;


import com.zx._12_算法.ListNode;

public class Demo4 {

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1, null);
        ListNode node1_1 = new ListNode(2, null);
        head1.next = node1_1;
        ListNode node1_2 = new ListNode(4, null);
        node1_1.next = node1_2;

        ListNode head2 = new ListNode(1, null);
        ListNode node2_1 = new ListNode(3, null);
        head2.next = node2_1;
        ListNode node2_2 = new ListNode(4, null);
        node2_1.next = node2_2;

        ListNode result = mergeTwoLists(head1, head2);

        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }

    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }

        // 进行对比的2个指针
        ListNode node1 = head1.val < head2.val ? head1 : head2;// 这个是保存结果的，最小值
        ListNode node2 = head1.val < head2.val ? head2 : head1;
        // 保存结果
        ListNode result = node1;
        while (true) {
            if (node2 == null) {
                break;
            }
            ListNode t1 = node1.next;
            ListNode t2 = node2.next;

            if (t1 == null) {
                node1.next = node2;
                break;
            }
            if (node1.val <= node2.val) {
                if (node2.val < t1.val) {
                    node1.next = node2;
                    node2.next = t1;

                    node1 = node1.next;
                    node2 = t2;
                } else {
                    node1 = node1.next;
                }
            }
        }

        return result;
    }


}
